package real.bytedance.dfs_bfs;
import java.util.*;

import org.junit.Test;
public class ExistingStrings {
    /*  
        给定一个字符矩阵，查询strs中每个字符是否可以在chs中搜索到
        搜索：第一个字符出现在[i, j]位置，此后只能进行上下左右四个方向的指针移动，四个方向都没有或者越界证明没有

        给定1个二维字符数组m和单词列表ws，搜索每个ws中的单词w是否在m中，返回所有在m的w。
        搜索的定义是从m的任意位置开始，可以上下左右移动，依次和w每个字符匹配，如果w能匹配完，则存在，否则不存在。

        例子： ["zoo", "zoro", "xtifx", "oto"]作为ws，返回的结果列表为["zoo", "zoro", "xtifx"]
        a c d z  

        x t r o  

        f i o o
    */
    boolean[][] flags;
    public List<String> isExist(List<String> strs, char[][] chs) {
        if (strs.size() == 0) return new ArrayList<>();
        Map<Character, List<int[]>> map = new HashMap<>();
        for (int i = 0; i < chs.length; i++) {
            for (int j = 0; j < chs[0].length; j++) {
                if (map.containsKey(chs[i][j])) {
                    map.get(chs[i][j]).add(new int[]{i, j});
                } else {
                    List<int[]> list = new ArrayList<>();
                    list.add(new int[]{i, j});
                    map.put(chs[i][j], list);
                }
            }
        }
        flags = new boolean[chs.length][chs[0].length];
        List<String> res = new ArrayList<>();
        loop: for (String s: strs) {
            List<int[]> idxes = map.get(s.charAt(0));
            for (int[] idx: idxes) {
                if (exists(chs, s, idx[0], idx[1], 0)) {
                    res.add(s);
                    continue loop;
                }
            }
        }
        return res;
    }
    List<int[]> mvs = new ArrayList<>(){{
        add(new int[]{0, 1});
        add(new int[]{1, 0});
        add(new int[]{-1, 0});
        add(new int[]{0, -1});
        }};
    public boolean exists (char[][] chs, String s, int i, int j, int idx) {
        if (idx == s.length()) return true;
        flags[i][j] = true;
        int cow, row;
        boolean res = false;
        for (int[] m: mvs) {
            if (inArea((cow = i + m[0]), (row = j + m[1])) && !flags[cow][row]) {
                res = res || exists(chs, s, cow, row, idx + 1);
                if (res) return true;
            }
        }
        flags[i][j] = false;
        return res;
    }

    public boolean inArea(int i, int j) {
        return i >= 0 && i < flags.length && j >= 0 && j < flags[0].length;
    }


    @Test
    public void test() {
        char[][] dict = new char[3][];
        dict[0] = new char[]{'a', 'c', 'd', 'z'};
        dict[1] = new char[]{'x', 't', 'r', 'o'};
        dict[2] = new char[]{'f', 'i', 'o', 'o'};

        List<String> list = new ArrayList<>(){{add("zoo");
                        add("zoro");
                        add("xtifx");
                        add("oto");}};

        List<String> res =  isExist(list, dict);
        System.out.println(res);

    }
}
